
#include "..\headers\ListOf.h"

// Define the structure of a linked list node
typedef struct ListNode {
  int data;
  struct ListNode* next;
} ListNode, *LinkList;

// Initialize the linked list
LinkList initList() { return NULL; }

// Insert an element into the linked list
LinkList insert(ListNode* head, int value) {
  LinkList newNode = (ListNode*)malloc(sizeof(ListNode));
  newNode->data = value;
  newNode->next = NULL;

  if (head == NULL) {
    head = newNode;
  } else {
    ListNode* temp = head;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = newNode;
  }
  return head;
}

// Merge two sorted linked lists
LinkList mergeLists(ListNode* list1, ListNode* list2) {
  LinkList mergedList = NULL;
  LinkList current = NULL;

  while (list1 != NULL && list2 != NULL) {
    if (list1->data <= list2->data) {
      if (mergedList == NULL) {
        mergedList = current = list1;
      } else {
        current->next = list1;
        current = current->next;
      }
      list1 = list1->next;
    } else {
      if (mergedList == NULL) {
        mergedList = current = list2;
      } else {
        current->next = list2;
        current = current->next;
      }
      list2 = list2->next;
    }
  }

  if (list1 != NULL) {
    if (mergedList == NULL) {
      mergedList = list1;
    } else {
      current->next = list1;
    }
  }

  if (list2 != NULL) {
    if (mergedList == NULL) {
      mergedList = list2;
    } else {
      current->next = list2;
    }
  }

  return mergedList;
}

// Print the linked list
void printList(LinkList head) {
  LinkList temp = head;
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

int main() {
  LinkList list1 = initList();
  LinkList list2 = initList();

  // Input elements for the first list
  int num1;
  printf("Enter the number of elements for the first list: ");
  scanf("%d", &num1);
  for (int i = 0; i < num1; ++i) {
    int value;
    scanf("%d", &value);
    list1 = insert(list1, value);
  }

  // Input elements for the second list
  int num2;
  printf("Enter the number of elements for the second list: ");
  scanf("%d", &num2);
  for (int i = 0; i < num2; ++i) {
    int value;
    scanf("%d", &value);
    list2 = insert(list2, value);
  }

  if (list1 == NULL && list2 == NULL) {
    printf("ERROR");
    return 0;
  }

  // Merge the two lists
  LinkList mergedList = mergeLists(list1, list2);

  // Print the merged list
  printf("Merged list:\n");
  printList(mergedList);

  return 0;
}
